#include <stddef.h>  // For size_t
#include <stdbool.h> // For bool type in optimized bubble sort

// 冒泡排序
void bubble_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) {
        return;
    }
    for (size_t i = 0; i < len - 1; ++i) {
        for (size_t j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 优化的冒泡排序
void opt_bubble_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) {
        return;
    }
    bool swapped;
    for (size_t i = 0; i < len - 1; ++i) {
        swapped = false;
        for (size_t j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

// 选择排序
void selection_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) {
        return;
    }
    for (size_t i = 0; i < len - 1; ++i) {
        size_t min_index = i;
        for (size_t j = i + 1; j < len; ++j) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

// 插入排序
void insertion_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) {
        return;
    }
    for (size_t i = 1; i < len; ++i) {
        int key = arr[i];
        size_t j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

// 二分插入排序
void bin_insertion_sort_int(int* arr, size_t len) {
    if (!arr || len == 0) {
        return;
    }
    for (size_t i = 1; i < len; ++i) {
        int key = arr[i];
        size_t left = 0;
        size_t right = i;
        while (left < right) {
            size_t mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        for (size_t j = i; j > left; --j) {
            arr[j] = arr[j - 1];
        }
        arr[left] = key;
    }
}